package com.xcc.dataStructures.leetcode;

/**
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(5 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：0 -> 1 -> 8
 * 原因：342 + 465 = 807
 * 345 465 = 810 0-1-8
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Demo004_LinkAddTwoNumbers {

    /**
     * 两个链表相加
     * @param l1    链表1
     * @param l2    链表2
     * @return  新的链表
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        ListNode result = null;
        //记录上一次的结余
        int last = 0;
        while (temp1 != null || temp2 != null) {
            int val1 = temp1 == null ? 0 : temp1.val;
            int val2 = temp2 == null ? 0 : temp2.val;
            int sum = last + val1 + val2;
            //加完之后清空
            last = 0;
            if (sum < 10) {
                result = addLast(result, sum);
            } else {
                last = 1;
                result = addLast(result, sum - 10);
            }
            temp1 = temp1 == null ? null : temp1.next;
            temp2 = temp2 == null ? null : temp2.next;
        }
        if (last > 0) {
            addLast(result, last);
        }
        return result;
    }

    /**
     * 往链表尾部加入数值
     * @param node  节点
     * @param val   值
     * @return  新的链表节点
     */
    public static ListNode addLast(ListNode node, int val) {
        ListNode listNode = new ListNode(val);
        if (node == null) {
            return listNode;
        }
        ListNode temp = node;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = listNode;
        return node;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(4);
//        ListNode node3 = new ListNode(3);
        node1.next = node2;
//        node2.next = node3;

        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(6);
        ListNode node6 = new ListNode(4);
        node4.next = node5;
        node5.next = node6;

        ListNode node = addTwoNumbers(node1, node4);
        show(node);

    }

    public static void show(ListNode node) {
        if (node == null) {
            return;
        }
        while (node.next != null) {
            System.out.print(node.val + "->");
            node = node.next;
        }
        System.out.println(node.val);
    }

}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}